// 力扣26. 删除有序数组中的重复项
// https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
package main

import (
	"fmt"
)

// 因为已经说了是排好序的数组，所以只需要不停判断当前位置值和下一位置值是否相等。
// 若相等则pop掉当前值，否则move到下一位置继续做判断。
// 时间复杂度是 O(n^2)，因为每一次pop操作都需要将被删除元素后面的所有元素向前移动一格。
func removeDuplicates1(nums []int) int {
	idx := 0
	for idx < len(nums)-1 {
		if nums[idx] == nums[idx+1] {
			nums = append(nums[:idx], nums[idx+1:]...) // 若相等则pop掉当前值
		} else { // 否则move到下一位置继续做判断
			idx += 1
		}
	}
	return len(nums)
}

// 不停地往后遍历数组，同时自增地分配不重复的值给前面的位置，对于重复的直接跳过。
// 时间复杂度就是O(n)。
func removeDuplicates2(nums []int) int {
	idx := 0
	for _, num := range nums {
		// 如果是第一位数,肯定不可能重复
		// 为了保证数组不越界,因此要判断 num != nums[idx-1]
		if (idx < 1) || (num != nums[idx-1]) {
			nums[idx] = num // 如果当前元素不是重复值，就将这个元素分配到目前不重复元素到达的index
			idx += 1
		}
	}
	return idx
}

func main() {
	fmt.Println(removeDuplicates1([]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4})) //5
	fmt.Println(removeDuplicates2([]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4})) //5
}
